/*
 * @lc app=leetcode.cn id=1514 lang=swift
 *
 * [1514] 概率最大的路径
 */

// @lc code=start
class Solution {
    func maxProbability(_ n: Int, _ edges: [[Int]], _ succProb: [Double], _ start: Int, _ end: Int) -> Double {
        var graph: [[(Int, Double)]] = Array(repeating: [], count: n+1)
        for i in 0..<edges.count {
            let from = edges[i][0]
            let to = edges[i][1]
            let prob = succProb[i]
            graph[from].append((to, prob))
            graph[to].append((from, prob))
        }

        return dijkstra(start, end, graph)
    }

    func dijkstra(_ start: Int, _ end: Int, _ graph: [[(Int, Double)]]) -> Double {
        var probs: [Double] = Array(repeating: -1, count: graph.count)
        probs[start] = 1

        var pq: [(Int, Double)] = []
        pq.append((start, 1))
        while !pq.isEmpty {
            let curNode = pq.removeFirst()
            let curNodeId = curNode.0
            let curNodeProb = curNode.1

            if curNodeId == end {
                return curNodeProb
            }

            if curNodeProb < probs[curNodeId] {
                continue
            }

            for nextNode in graph[curNodeId] {
                let nextNodeId = nextNode.0
                let nextNodeProb = curNodeProb * nextNode.1
                if nextNodeProb > probs[nextNodeId] {
                    probs[nextNodeId] = nextNodeProb
                    pq.append((nextNodeId, nextNodeProb))
                    pq.sort(by: { a, b in a.1 > b.1 })
                }
            }
        }

        return 0
    }
}
// @lc code=end

